Zoekboom

Een zoekboom in de informatica is een boomstructuur die gebruikt wordt voor het vinden van specifieke waarden uit een verzameling. Een belangrijke eigenschap die een zoekboom van een gewone boom onderscheidt is het gegeven dat de waarde van een top groter moet zijn dan de waarden in de linkersubboom en kleiner dan de waarden in de rechtersubboom.^[1]

Het voordeel van zoekbomen is hun efficiënte zoekoperatie, gegeven dat de boom redelijk gebalanceerd is. Dit wil zeggen dat de bladeren van de boom allemaal ongeveer even diep zitten. Er bestaan verschillende soorten zoekbomen; verschillende soorten hebben ook efficiënte toevoeg- en verwijderoperaties.

Zoekbomen worden vaak gebruikt om een associatieve array te implementeren. Dit kan door de sleutels van de sleutel/waarden-paren uit de array te gebruiken als waarden voor de toppen in de boom.

1. ↑ (en) Black, Paul, search tree. Dictionary of Algorithms and Data Structures (14 december 2005). Geraadpleegd op 28 maart 2019.